//
// Created by sjjmw on 3/24/2022.
//

//应该使用dfs

#include "iostream"
#include "vector"
#include "list"
#include "algorithm"
#include "string"
#include "unordered_map"
#include "cmath"
#include<iomanip>
#include "string"
#include "map"
#include "list"

//最后还是ac了。
//记忆
//加教室，dfs一层一个学生
//1.尝试加入到之前的教室
//2.尝试开新教室
struct Sol{
    std::vector<std::vector<char>> gxb;
    std::vector<char> selected;
    std::vector<std::list<int>> classes;
    int class_cnt=1;
    int minclass=INT_MAX;
    void dfs(int selcnt){
        if(class_cnt>minclass){
            return;
        }
        if(selcnt==selected.size()){
            if(class_cnt<minclass){
                minclass=class_cnt;
            }
            return;
        }
        int i=selcnt;//当前学生
//        for(int i=0;i<selected.size();i++){
//            if(!selected[i]){
//                selected[i]=1;
//                bool hasrs=false;
                int cantinclass=0;
                for(int c=0;c<class_cnt;c++){
                    bool hasrs=false;
                    for(auto st:classes[c]){
                        if(gxb[st][i]==1){
                            hasrs= true;
                        }
                    }
                    if(hasrs){
                        cantinclass++;
                    }else{
                        classes[c].push_back(i);
                        dfs(selcnt+1);
                        classes[c].pop_back();

                    }
                }
                if(class_cnt+1<minclass){
                    if(class_cnt+1>classes.size()){
                        classes.push_back(std::list<int>());
                    }
                    class_cnt++;
                    classes[class_cnt-1].push_back(i);
                    dfs(selcnt+1);
                    classes[class_cnt-1].pop_back();
                    class_cnt--;
                }
//                if(cantinclass==class_cnt){
//                    classes.pop_back();
//                }
//                if(hasrs){
//                    classes.push_back(std::vector<int>());
//                }
//                classes[classes.size()-1].push_back(i);
//                dfs(selcnt+1);
//                if(hasrs){
//                    classes.pop_back();
//                }
//                selected[i]=0;
//            }
//        }
    }
    void handle(
            int n,int m
            ){
        std::vector<char> gxbline(n);
        selected.resize(n);
        for (int i = 0; i < n; ++i) {
            gxb.push_back(gxbline);
        }
        for(int i=0;i<m;i++){
            int a,b;std::cin>>a>>b;
            gxb[a-1][b-1]=1;
            gxb[b-1][a-1]=1;
        }
        classes.reserve(10000000);
        classes.push_back(std::list<int>());
        dfs(0);
        printf("%d\n",minclass);
    }
};
int main(){
    int a,b,c;
//    float a,b,c,d;
    int e;
    while(std::cin>>a>>b){
        Sol().handle(a,b);

//        Sol().handle(a,b);
    }

    return 0;
}